// 236. 二叉树的最近公共祖先
// 给定一个二叉树, 找到该树中两个指定节点的最近公共祖先。

// 百度百科中最近公共祖先的定义为：“对于有根树 T 的两个节点 p、q，
// 最近公共祖先表示为一个节点 x，满足 x 是 p、q 的祖先且 x 的深度尽可能大
// （一个节点也可以是它自己的祖先）。”

// 输入：root = [3,5,1,6,2,0,8,null,null,7,4], p = 5, q = 1
// 输出：3
// 解释：节点 5 和节点 1 的最近公共祖先是节点 3 。
/**
 * Definition for a binary tree node.
 * function TreeNode(val) {
 *     this.val = val;
 *     this.left = this.right = null;
 * }
 */
/**
 * @param {TreeNode} root
 * @param {TreeNode} p
 * @param {TreeNode} q
 * @return {TreeNode}
 */
 var lowestCommonAncestor = function(root, p, q) {
    const def=function(root,p,q){
        // 如果找到了 节点p或者q，或者遇到空节点，就返回。
        if(root==null||root==q||root==p) return root;
        // 要遍历整棵树 即使此时已经找到了目标节点了 还要遍历根节点右子树
        let leftNode=def(root.left,p,q);
        let rightNode=def(root.right,p,q);
        // 如果left 和 right都不为空，说明此时root就是最近公共节点。
        if(leftNode!==null&&rightNode!==null) return root;
        // 如果left为空，right不为空，就返回right，说明目标节点是通过right返回的
        if(leftNode===null) return rightNode;
        // 反之依然。
        return leftNode;
    }
    return def(root,p,q);
};